이산수학(discrete mathematics)에 대한 개념정리

안녕하세요 클래스메소드 코리아의 김재욱입니다.

이번에는 프로그래밍을 하다 보면 알게 모르게 사용되어왔던 이산수학(discrete mathematics)에 대해서 정리해 보았습니다.

이산수학(discrete mathematics)이란?

이산수학(Discrete mathematics, 離散數學)은 이산적인 수학 구조에 대해 연구하는 학문으로, 연속되지 않는 공간을 다룬다. 유한수학이라고도 하며, 전산학적인 측면을 강조할 때는 전산수학이라고도 한다.

이산수학은 기초적인 학문이기 때문에 어디에 사용해야하는지, 왜 사용해야하는지 잘 모르는 경우가 많습니다. 하지만 프로그래밍을 하다보면 자기도 모르게 이산수학을 사용하는 경우가 있습니다. 예를 들어 명제, 재귀, 함수, 그래프, 트리, 탐색과 같은 부분은 프로그래밍을 하면서 자연스럽게 사용하게 됩니다. 오늘은 이러한 이산수학에 대해서 정리해 보고자합니다.

다중한정기호

중첩된 한정기호는 ∀x∃y (x + y = 0) 와 같이 여러개의 한정기호가 한 명제 안에 쓰인 것을 말합니다.

공리 - 증명 과정 없이 참이라고 간주되는 명제

ex)별개인 2개의 점이 주어졌을 때 두점을 잇는 선은 정확히 1개

정의 - 기존의 개념을 이용하여 만들어진 새로운 개념

ex) 측정 값이 합이 180도이면 두 각은 서로 여각이다

정리 - 참이라고 증명된 명제

ex) 만약 삼각형의 두변이 같다면, 이둘이 마주보고 있는 각도가 같다

보조정리 - 다른 정리를 증명하는데 유용하게 사용되는 정리

ex) 만약 삼각형이 이등변 삼각형이라면, 두 각이 같다

정리의 일반형태

"모든 x1,x2....xn에 대하여 만약 p(x1,x2....xn)이면 q(x1,x2....xn)이다"

직접증명 (가설 p -> 결론 q)

• p(x1,x2...xn)을 참이라 가정
• p(x1,x2...xn)과 공리,정의 정리, 추론규칙 등을 이용하여 전개
• q(x1,x2..xn)이 참임을 보인다.

정의 : 짝수와 홀수

"만약 n=2k가 되는 정수 k가 존재하면 정수 n은 짝수이다

만약 n = 2k+1가 되는 정수 k가 존재하면 정수n은 홀수이다."

예제 - 직접증명

"정수 n=12는 짝수이다"

(증명) n=2k가 되는 정수k(즉, k=6)이 존재한다.

"모든 정수 m,n에 대하여 만약 m이 홀수이고 n이 짝수이면 m+n은 홀수이다"

(증명) m이 홀수 : m = 2k1+1이 되는 k1 존재, n이 짝수 n=2k2 가 되는 k2 존재

• m+n = (2k1+1) + (2k2) = 2(k1+k2)+1
• 그러므로 m+n은 홀수이다

"모든 집합 X와 Y에 대해서 Xu(Y-X) = XuY이다"

(증명) XU(Y-X) = Xu(YnX(여집합)) <- Y-X = Y n X(여집합)

= (X u Y) n (X u X(여집합)) <- 분배법칙

= (X u Y) n U <- 여집합 법칙

= X u Y <- 항등법칙

반례에 의한 증명

∀xP(x)를 반증하는 것은 P(x)를 거짓으로 만드는 논의 영역에 속한 하나의 원소 x를 보이는 것이다.

이러한 역할을 하는 원소 x를 반례라고 한다.

ex)"∀n∈Z+ (2의n승+1은 소수)"

(증명) 위의 명제 n=3의 반례가 존재 하므로 거짓이다

• n = 3 일 때 2의3승+1 = 8 + 1 = 9 는 약수 1, 3, 9를 갖는다.
• ∀n∈Z+에 대하여 2의n승 + 1 은 소수가 아니다

모순에 의한 증명

모순 - (r ∧ㄱr) 형태의 명제

p->q을 증명하는 대신 다음을 증명한다  (p ∧ㄱq) -> (r ∧ㄱr)

예제 - 모순에 의한 증명

"모든 n∈Z에 대하여 만약 n제곱이 짝수이면 n이 짝수이다"

(증명) n제곱이 짝수(가설)이고 n이 홀수(부정된 결론)이라고 가정하자

• (결론에서) n이 홀수 이므로 n = 2k+1이 되는 k 존재
• (가설에서) n제곱 = (2k+1)제곱 = 4k제곱 + 4k+1 = 2(2k제곱 + 2k)+1 = 2(k')+1
• 그러므로 n제곱은 홀수이며 n제곱이 짝수라는 명제의 가설과 모순이다
• 모든 n∈Z에 대하여 만약 n제곱이 짝수이면 n이 짝수임을 증명

대우에 의한 증명

대우 : p->q 와 ㄱq->ㄱp의 관계로서 논리적 동치

p->q을 증명하는 대신 다음을 증명한다

ㄱp->ㄱq

예제 - 대우에 의한 증명

"모든 x∈R에 대하여 만약 x제곱이 무리수이면 x는 무리수이다"

(증명) 대우 : "만약 x가 무리수가 아니라면 x제곱은 무리수가 아니다"

• "만약 x가 유리수라면 x제곱은 유리수이다"
• x는 어떤 정수 p,q에 대해서 x = p/q이다
• x제곱 = p제곱/q제곱
• x제곱은 정수의 분수 꼴이므로 유리수이다

경우에 의한 증명

본래의 가설이 여러가지 경우로 분할될 때 각 경우에 대하여 증명

(p1∧p2∧...pn)->q를 증명하는 대신 다음을 증명

(p1->q)V(p2->q)V.....V(pn->q)

예제 - 경우에 의한 증명

"모든 m,n∈Z에 대하여 2m제곱+3n제곱=40은 정수해를 갖지 않는다."

(증명) 만약 2m제곱+3n제곱=40 이라면, 2m제곱 <= 40, 3n제곱 <= 40이다.

• m제곱 <= 20 , n제곱 <= 40/3
• m <= 4 , n <= 3
• 2m제곱+3n제곱≠40 if m <= 4, n <= 3

2m제곱 + 3n제곱 > 40 if m > 4, n > 3

• 해가 존재하지 않음

동치에 의한 증명

p if and only if q 형태의 정리에 대하여 증명

p<->q을 증명하는 대신 다음을 증명 (p->q)∧(q->p)

예제 - 동치에 의한 증명

"모든 n∈Z에 대하여 n이 홀수임과 n-1이 짝수임은 서로 동치이다"

(증명) "n이 홀수이면 n-1이 짝수이다"

• n이 홀수이면 n = 2k+1이므로 n-1 = (2k+1)-1 = 2k
• n-1은 짝수임

"n-1이 짝수이면 n이 홀수이다"

• -> n-1이 짝수이면 n-1=2k이므로 n = 2k+1
• n은 홀수임

존재의 증명

∃xp(x)에 대한 증명

p(x)를 참으로 만드는 논의 영역의 요소 x를 찾는다

예제 - 존재의 증명

"2p-1 이 합성수가 되는 소수 p가 존재한다"

(증명) 시행착오 방법으로 증명

• p = 2 이면 2의 2승 -1 = 4 -1 = 3 -> 소수
• p = 3 이면 2의 3승 -1 = 8 - 1 = 7 -> 소수
• p = 5 이면 2의 5승 -1 = 32 - 1 = 31 -> 소수
• p = 7 이면 2의 7승 -1 = 128 - 1 = 127 -> 소수
• p = 11이면 2의 11승 - 1 = 2048 - 1 = 2047 = 23x89 -> 소수가 아님

수학적 귀납법

n개의 양의 정수에 대해서 명제 S(n)이 존재 한다고 하자

모든 양의 정수 n에 대하여 S(n)이 참이 되려면 다음 두 조건이 만족 되어야 한다

• S(1)이 참이다
• 모든 n>=1에 대하여 S(n)이 참이 되려면 S(n+1)도 참이다

예제 - 수학적 귀납법

"Sn = 1+2+....+n 이라고 하자 그러면 모든 n>=1 에 대하여 Sn = n(n+1)/2이다"

(증명) 1. n = 1 일때 Sn=1, Sn = n(n+1)/2 = 1(1+1)/2 = 1

1. n>=1에 대하여 Sn이 참이라고 가정하고 Sn+1을 점검하자

• Sn+1 = 1+2+...+n+(n+1)
• = Sn + (n+1)
• = n(n+1)/2 + (n+1) = n(n+1)/2 + 2(n+1)/2
• = (n+1)(n+2)/2

정의 - n 계승

n! = 1               if n = 0

n(n+1)(n-2)        if n >= 1

예제 수학적 귀납법

"모든 n>=1에 대하여 ni>=2n-1이다"

(증명) 1. n=1일 때, n! = 1 >=2 1승-1승 = 1

1. n>=1 에 대하여 n!>=2n-1이 참이라고 가정하고 (n+1)!을 점검하자

• (n+1)! = (n+1)n!
• >= (n+1) 2n-1
• >= (2)2n-1
• = 2n

함수

함수 f : X->Y

집합 X에서 집합 Y로의 함수 f는

• 각각의 x∈X에 대하여
• (x,y)∈f인 정확히 하나의 y∈Y가 존재하는 성질을 만족시키는 데카르트 곱 XxY의 부분집합

정의역 X

공변역 Y

치역 {y l (x,y) ∈ f}

나머지 연산자

x가 정수이고 y가 양의 정수 일때, x mod y 를 x를 y로 나누었을때의 나머지들로 정의

ex) 6 mod 4 = 2 , 5 mod 4 = 1, 8 mod 12 = 8

해시함수

처리 대상 데이터의 숫자는 적지만 데이터 범위가 큰 경우 사용

h(n) = n mod k         k :  number of memory cells

ex) n= 15, 558 , 32, 257, 102, 74       k = 10

의사난수

선형 합동법

X0 = s(Seed)

Xn = (Axn-1 + C) mod m         2 <= a < m, 0<= c < m, 0 <= s < m

ex) m = 11, a = 7, c = 5, s = 3

• X0 = S = 3
• X1 = (Ax0 + c) mod m = (7 * 3 + 5) mod 11 = 4
• X2 = (Ax1 + c) mod m = (7 * 4 + 5) mod 11 = 0
• X3 = (Ax2 + c) mod m = (7 * 0 + 5) mod 11 = 5
• X4 = (Ax3 + c) mod m = (7 * 5 + 5) mod 11 = 7
• X5 = (Ax4 + c) mod m = (7 * 7 + 5) mod 11 = 10
• X6 = (Ax5 + c) mod m = (7 * 10 + 5) mod 11 = 9
• X7 = (Ax6 + c) mod m = (7 * 9+ 5) mod 11 = 2

Floor 함수와 ceil 함수

Floor 함수 : x보다 크거나 같은 최대의 정수

ceil 함수 : x보다 크거나 같은 최소의 정수

ex) floor [1.4] = 1, [0.9] = 0, [-1.4] = -2

ex) ceil [1.4] = 2, [0.9] = 1, [-1.4] = -1

관계의 성질

관계

집합 X에서 집합 Y로의 (이항) 관계 R은 데카르트곱 XxY 의 부분 집합

"x와 y가 관계가 있다" - (x,y) ∈ R 또는 xRy

X = Y 인 경우, R은 X에서의 (이항)관계

ex) X = {2,3,4} Y = {3,4,5,6,7}, R:x∈X 가 y∈Y를 나누면 (x,y)∈R

-> R : {(2,4),(2,6),(3,3),(3,6),(4,4)}

예제 - 관계

ex) X = {1,2,3,4} r : x,y∈X 에서 x<=y이면 (x,y)∈R

-> R= {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

예제 = 관계

ex) X = {a,b,c,d} R = {(a,a),(b,c),(c,b),(d,d)}

반사적 관계

집합 X에서의 관계 R이 X의 모든 원소 x에 대해 (x,x)∈R임

∀x[x∈X] -> [(x,x)∈R]

ex) X = {1,2,3,4}

R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

ex) X = {a,b,c,d} R = {(a,a),(b,c),(c,b),(d,d)} 비반사적

대칭적 관계

집합 X에서의 관계 R이 모든 x,y∈R에 대해서 (x,y)∈R일 때 (y,x)∈R임

∀x∀y[(x,y)∈R] -> [(y,x)∈R]

ex) X = {1,2,3,4}

R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} (비대칭적)

ex ) X = {a,b,c,d}

X = {a,b,c,d} R = {(a,a),(b,c),(c,b),(d,d)} (대칭적)

반대칭적 관계

집합 X에서의 관계 R이 모든 x,y∈R에 대해(x,y)∈R일 때 (y,x)∈R이면 x=y이다

∀x∀y[(x,y)∈R∧(y,x)∈R] -> [x=y]

모든 x,y∈R에 대해 x≠y이면 (x,y)∉R이거나 (y,x)∉R이다

-> "만약 원소쌍 x,y∈R가 대칭적 관계에 속하면, 이들은 동일한 원소이다.

동일한 원소에 대한 관계가 아니면, 대칭적 관계가 존재하지 않는다."

-> "반 대칭적관계는 대칭적 관계의 특수한 형태"

ex) X = {1,2,3,4} , R:x,y∈X에서 x<=y 이면 (x,y)∈R

-> R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

->반대칭적

추이적 관계

집합 X에서의 관계 R이 모든 x,,y,z∈X에 대해 (x,y)∈R이고 (y,z)∈R이면 (x,z)∈R

∀x∀y∀z[(x,y)∈R∧(y,z)∈R] -> [(x,z)∈R]

ex) X = {1,2,3,4}, R : x,y∈X에서 x<=y이면 (x,y)∈R

-> R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

(1,1),(2,2),(3,3),(4,4) 하지만 (3,2),(4,3) 처럼 반대로 가는것이 아니다 그러므로 반대칭형이다.

반순서 관계

집합 X에서의 관계 R이 반사적, 반대칭적, 추이적이다

집합X의 원소들을 순서화하는 것이 가능하다

ex) X = {1,2,3,4} R : x,y,z∈X에서 x<=y이면 (x,y)∈R

-> R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

ex)양의 정수의 집합에서 나누기 관계(반순서적)

->2와 3은 비교불가능 하다 그러나 2와 6, 3과 6은 비교 가능

전순서 관계

집합 X에서의 관계 R이 반사적,반대칭적,추이적이며, 집합 X의 모든 원소들이 비교가능하다.

ex)양의 정수(Z+)의 집합에서 작거나 같은 (x<=y)관계는 전순서적이다.

점화 알고리즘

알고리즘의 분석

크기가 n인 모든 입력에 대하여 알고리즘을 실행하는데 필요한 시간

• 최선 경우의 시간
• 최악 경우의 시간
• 평균 경우의 시간

ex) 크기 n = 1000인 숫자 데이터 가운데서 원하는 숫자 데이터를 찾아내는 경우 필요한 시간

• 최선 경우의 시간 = 1
• 최악 경우의 시간 = 1000평균 경우의 시간 = 500

빅오(O), 오메가(Ω), 세타(Θ) 함수

f와 g를 정의역 {1,2,3}에서 정의된 함수라고 할 때, 유한개를 제외한 모든 양의 정수 n에 대하여 다음 조건에 따른 표기법을 사용

l f(n) l <= C1 l g(n) l 를 만족하는 양의 상수 C1이 존재하면

f(n) = O(g(n))

-> " f(n)은 g(n)의 빅오(O) 함수, f(n)은 최대한 g(n) 차수"

l f(n) l >= C2 l g(n) l 를 만족하는 양의 상수 C2 가 존재하면 f(n) = Ω(g(n))

->" f(n)은 g(n)의 오메가 함수, f(n)은 최소한 g(n)의 차수"

f(n) = O(g(n))이고 f(n) = Ω(g(n))이면,

f(n) = Θ(g(n))

->"f(n)은 g(n)의 세타(Θ)함수, f(n)은 g(n) 차수"

예제 - 빅오(O), 오메가(Ω), 세타(Θ) 함수

f(n) = 60n2+5n+1

빅오(O)함수 l f(n) l <= C1 l g(n) l

f(n) = 60 n2+5n+1 <= 60n2 + 5n2 + n2 = 66n2

-> C1 = 66, 60n2 + 5n2+1 = O(n2)

오메가(Ω) 함수 l f(n) l >= C2 l g(n) l

모든 n >= 1 에 대하여 f(n) = 60n2 + 5n + 1 >= 60n2

-> C2 = 60, 60n2 + 5n + 1 = Ω(n2)

세타(Θ) 함수 f(n) = O(g(n)) 이고 f(n) = Ω(g(n))

60n2 + 5n + 1 = O(n2) , 60n2 + 5n + 1 = Ω(n2)

-> 60n2 + 5n + 1 = Θ(n2)

마지막으로

이산수학(discrete mathematics)의 기본개념에 대해서 정리해 보았는데요, 이것 외에도 관계 행렬, 알고리즘, 역관계, 합성관계, 동치관계 등등 다양하게 있지만 다 정리하자면 내용이 길어지기 때문에 점화 알고리즘까지만 정리 해보았습니다! 혹시라도 이산수학(discrete mathematics)에 관심이 있다거나, 배우고 싶다는 분들에게 도움이 됐으면 좋겠습니다.